package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 106. 从中序与后序遍历序列构造二叉树
 * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * <p>
 * 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
 * 输出：[3,9,20,null,null,15,7]
 * 示例 2:
 * <p>
 * 输入：inorder = [-1], postorder = [-1]
 * 输出：[-1]
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= inorder.length <= 3000
 * postorder.length == inorder.length
 * -3000 <= inorder[i], postorder[i] <= 3000
 * inorder 和 postorder 都由 不同 的值组成
 * postorder 中每一个值都在 inorder 中
 * inorder 保证是树的中序遍历
 * postorder 保证是树的后序遍历
 */
public class BuildTree1 {


    private Map<Integer, Integer> indexMap;

    public static void main(String[] args) {

        int[] aa = {9, 3, 15, 20, 7};
        int[] bb = {9, 15, 7, 20, 3};
        new BuildTree1().buildTree(aa, bb);
    }

    /**
     * 思路对了 细节有点问题
     *
     * @param inOrder
     * @param postOrder
     * @return
     */
    public TreeNode buildTree(int[] inOrder, int[] postOrder) {

        if (inOrder == null) {
            return null;
        }
        int n = inOrder.length;
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inOrder[i], i);
        }
        return myBuildTree(postOrder, inOrder, 0, n - 1, 0, n - 1);

    }


    public TreeNode myBuildTree(int[] postOrder, int[] inOrder, int postorder_left, int postorder_right, int inorder_left, int inorder_right) {
        if (postorder_left > postorder_right) {
            return null;
        }

        // 后序遍历中的倒数第一个节点就是根节点
        int postorder_root = postorder_right;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(postOrder[postorder_root]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(postOrder[postorder_right]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        root.left = myBuildTree(postOrder, inOrder, postorder_left, postorder_left + size_left_subtree - 1, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        root.right = myBuildTree(postOrder, inOrder, size_left_subtree + 1, postorder_right - 1, inorder_root + 1, inorder_right);
        return root;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
